package leetcode_1101_1200;

import com.sun.org.apache.xpath.internal.operations.Bool;

import java.util.ArrayList;
import java.util.List;

public class LeeCode_1177 {
    public static void main(String[] args) {
        System.out.println(canMakePaliQueries("abcda", new int[][]{{0, 4, 1}}));
    }
    private static List<Boolean> canMakePaliQueries(String s, int[][] queries) {
        int n = s.length();
        int[][] cs = new int[26][n + 1];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            for (int j = 0; j < 26; j++) {
                if (j == c - 'a'){
                    cs[j][i + 1] = cs[j][i] + 1;
                }else
                    cs[j][i + 1] = cs[j][i];
            }
        }
        List<Boolean> ans = new ArrayList<>();
        for (int[] query : queries) {
            int l = query[0], r = query[1], k = query[2], c = 0;
            for (int i = 0; i < 26; i++) {
                if ((cs[i][r + 1] - cs[i][l]) % 2 == 1){
                    c++;
                }
            }
            if ((r - l + 1) % 2 == 1){
                ans.add((c - 1) / 2 <= k);
            }else {
                ans.add(c / 2 <= k);
            }
        }
        return ans;
    }
}
